package Offer;

/**
 * II. 青蛙跳台阶问题
 * @author 是阿秋啊
 * @date 2022/04/06 21:33
 **/
public class Num10II {
    public int numWays(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] sum = new int[n];
        sum[0] = 1;
        sum[1] = 2;
        return helper(sum,n - 1);
    }

    private int helper(int[] sum, int n) {
        if (sum[n] > 0) {
            return sum[n];
        }
        return (helper(sum,n - 1) + helper(sum, n - 2)) % 1000000007;
    }
}
